class Solution:
    def findItinerary(self, tickets):
        def bsf(ticketSet, ticketHash, r):
            if len(ticketSet) == 0:
                return r
            if r[-1] not in ticketHash:
                return None
            tmpList = ticketHash[r[-1]]
            for i in tmpList:
                if (r[-1],i) not in ticketSet:
                    continue
                num = ticketSet[(r[-1],i)]
                if num>1:
                    ticketSet[(r[-1], i)] -= 1
                else:
                    ticketSet.pop((r[-1],i))
                r.append(i)
                ri = bsf(ticketSet,ticketHash,r)
                if ri is not None:
                    return ri
                r.pop(-1)

                if (r[-1],i) not in ticketSet:
                    ticketSet[(r[-1], i)] = 1
                else:
                    ticketSet[(r[-1], i)] += 1

            return None


        ticketHash = {}
        ticketSet = {}
        for i in tickets:
            if i[0] not in ticketHash:
                ticketHash[i[0]] = set()
            ticketHash[i[0]].add(i[1])
            if (i[0],i[1]) not in ticketSet:
                ticketSet[(i[0],i[1])] = 0
            ticketSet[(i[0], i[1])] += 1
        for key in ticketHash:
            l = list(ticketHash[key])
            l.sort()
            ticketHash[key] = l
        # print(ticketHash)
        # print(ticketSet)

        r = ['JFK']
        return bsf(ticketSet, ticketHash, r)



if __name__ == '__main__':
    so = Solution()
    tickets =  [["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"],["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
    r = so.findItinerary(tickets)
    print(r)
